

class Solution:

    def maximalRectangle(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        max_res = 0
        heights = [0] * len(matrix[0])
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == '1':
                    heights[j] += 1
                else:
                    heights[j] = 0
            max_res = max(max_res, self.largestRectangleArea(heights))
        return max_res

    def largestRectangleArea(self, heights):
        stack = [-1]
        max_res = 0
        for i in range(len(heights)):
            while len(stack) > 1 and heights[i] < heights[stack[-1]]:
                max_res = max(max_res, heights[stack.pop()] * (i - 1 - stack[-1]))
            stack.append(i)
        for i in range(len(stack)-1):
            max_res = max(max_res, heights[stack.pop()] * (len(heights) - 1 - stack[-1]))
        return max_res


res = Solution().maximalRectangle([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]])
print(res)